//
//  MaxCommonDivisorControl.swift
//  AlgorithmDEMO
//
//  Created by meitianhui2 on 2018/1/15.
//  Copyright © 2018年 DeLongYang. All rights reserved.
/*
    使用 swift 3.0 或以上 语法 编写
    总共使用 了三种 方法  一种遍历的方法  一种 辗转相除法 一种辗转想减法
 */

import UIKit

class MaxCommonDivisorControl: BaseControl {
    
    
    /// 第一种 方法 如果两个数 都不是 很大 的情况下
    override func executeAlgorithm() {
        
        // 求 98 和  63 的最大公约数
        let a:Int = 98
        let b:Int = 63
        
        // 求出二种中的 最小值
        let n:Int = a > b ? b:a
        for i in (2...n).reversed(){
            // 逐个遍历 数值  然后 分别计算
            if a%i == 0 && b%i == 0{
                print("最大公约数是: \(i)")
                break;
            }
//            print("--")
        }
        
    }
    
    
    /// 第二种 方法  辗转相除法   又叫 欧几里得算法
    //  当两个数的 较大时  使用 第一种有可能影响 性能 这种方法能减少计算次数
    override func executeAlgorithmTwo() {
        
        // 第一步 我们知道 a 大于 b 如果不知道的话 我们要分辨出来
        var a:Int = 8251
        var b:Int = 6105
        
        while  a%b != 0 {
//            let q:Int = a/b
            let m = b
            let n = a%b
            a = m
            b = n
            
        }
        
        print("second method 最大公约数是: \(b)")
        // 37 很明显 能明显的减少计算的次数
        
    }
    
    /// 第三种 计算的方法  辗转相减法  最早源自九章算术
    //  给定两个正整数 判断是否都是偶数 如果是 用2约简 如不是  较大数减去较小的数
    //  差和较小的数比较 用较大的数 减去较小的数 知道所得的数相等为止 相等的数就是最大公约数
    override func executeAlgorithmThree() {
        
        // 求 98 和  63 的最大公约数
        var a:Int = 98
        var b:Int = 63
        
        
        if a%2 == 0 && b%2 == 0
        {
            a = a/2
            b = b/2
        }
        else
        {
            // 求出二者的最大值 把大值给 a 把小值给 b
            let max = a>b ? a:b
            let min = a<b ? a:b
            a = max
            b = min
            
            //
            while a - b != 0{
                let diff = a - b
                var maxIn = 0
                var minIn = 0
                // 求出 最小的差值 然后继续减
                if diff > b{
                    maxIn = diff
                    minIn = b
                }else{
                    maxIn = b
                    minIn = diff
                }
                
                a = maxIn
                b = minIn
            }
        }
        print("three method 最大公约数是 \(b)")
    }

}



























































